package leetcode_ago.bin_tree;

public class Num106_BuildTreeByPostAndIn {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //后序序列进行转置将左右根变为根右左，此时就和前序中序求二叉树做法类似
        int[] resOrder=reverse(postorder);
        return buildTreeHelper(resOrder,inorder,0,resOrder.length-1);
    }
    //当前转置后的后序遍历序列正在处理哪个节点
    private int index=0;
    private TreeNode buildTreeHelper(int[] resOrder, int[] inorder, int left, int right) {
        //再转制后的后续遍历列表中取出根节点
        //通过根节点在中序遍历序列中找根节点在中序遍历中的位置
        //通过位置划分左右孩子-由于转置得到的结果，先遍历右孩子：根右左
        //1.边界
        if(left>right){
            return null;
        }
        if(index==resOrder.length){
            return null;
        }
        //2.创建根节点
        TreeNode root=new TreeNode(resOrder[index]);
        index++;
        //3.找到根节点在中序遍历的位置
        int pos=find(root.val,inorder);
        //4.处理右孩子和左孩子
        root.right=buildTreeHelper(resOrder,inorder,pos+1,right);
        root.left=buildTreeHelper(resOrder,inorder,left,pos-1);
        return root;
    }

    private int find(int val,int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }

    private int[] reverse( int[] postorder) {
        int left=0;
        int right=postorder.length-1;
        while(left<right){
            int temp=postorder[left];
            postorder[left]=postorder[right];
            postorder[right]=temp;
            left++;
            right--;
        }
        return postorder;
    }
}
